#pragma once
#include<vector>
#include<string>

using namespace std;

inline unsigned long __stl_next_prime(unsigned long n)
{
	// Note: assumes long is at least 32 bits.
	static const int __stl_num_primes = 28;
	static const unsigned long __stl_prime_list[__stl_num_primes] =
	{
		53, 97, 193, 389, 769,
		1543, 3079, 6151, 12289, 24593,
		49157, 98317, 196613, 393241, 786433,
		1572869, 3145739, 6291469, 12582917, 25165843,
		50331653, 100663319, 201326611, 402653189, 805306457,
		1610612741, 3221225473, 4294967291
	};
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}



template<class T>
struct HashNode
{
	T _data;
	HashNode* _next;

	HashNode(const T& data)
		:_data(data),
		_next(nullptr)
	{

	}
};

template<class K, class T, class KeyofT, class Hash>
class HashTable;

template<class K ,class T,class Ptr,class Ref,class KeyofT,class Hash>
struct HTIterator
{
	typedef HashNode<T> Node;
	typedef HTIterator<K,T, Ptr, Ref, KeyofT, Hash> self;
	typedef HashTable<K, T, KeyofT, Hash> HT;

	Node* _node;
	const HT* _ht;

	HTIterator(Node* node, const HT* ht)
		:_node(node),
		_ht(ht)
	{

	}

	Ref operator*()
	{
		return (_node->_data);
	}

	Ptr operator->()
	{
		return &(_node->_data);
	}

	self operator++()
	{
		Node* cur = _node;
		if (cur->_next)
		{
			_node = _node->_next;
			return *this;
		}
		else
		{
			size_t Hashi = Hash()(KeyofT()(_node->_data)) % _ht->_tables.size();
			Hashi++;
			while (Hashi<_ht->_tables.size())
			{
				if (_ht->_tables[Hashi])
				{
					break;
				}
				else
				{
					Hashi++;
				}

			}

			if (Hashi == _ht->_tables.size())
			{
				_node = nullptr;
			}
			else
			{
				_node = _ht->_tables[Hashi];
			}
		}
		return *this;
	}

	bool operator==(const self& s)
	{
		return s._node == _node;
	}

	bool operator!=(const self& s)
	{
		return s._node != _node;
	}
};

template<class K,class T,class KeyofT,class Hash>
class HashTable
{
	template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
	friend struct HTIterator;

	typedef HashNode<T> Node;
public:
	typedef HTIterator<K, T, T*, T&, KeyofT, Hash> Iterator;
	typedef HTIterator<K, T, const T*, const T&, KeyofT, Hash> ConstIterator;

	HashTable()
		:_tables(__stl_next_prime(1), nullptr)
		, _n(0)
	{
	}

	Iterator Begin()
	{
		size_t Hashi = 0;
		while (Hashi < _tables.size())
		{
			if (_tables[Hashi])
			{
				return Iterator(_tables[Hashi], this);
			}

			Hashi++;
		}

		return Iterator(nullptr, this);
	}

	Iterator End()
	{
		return Iterator(nullptr, this);
	}

	ConstIterator Begin() const
	{
		size_t Hashi = 0;
		while (Hashi < _tables.size())
		{
			if (_tables[Hashi])
			{
				return Iterator(_tables[Hashi], this);
			}

			Hashi++;
		}

		return ConstIterator(nullptr, this);
	}

	ConstIterator End() const
	{
		return ConstIterator(nullptr, this);
	}

	~HashTable()
	{
		for (size_t Hashi = 0; Hashi < _tables.size(); Hashi++)
		{
			if (_tables[Hashi])
			{
				Node* cur = _tables[Hashi];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[Hashi] = nullptr;
			}
		}
	}

	pair<Iterator, bool> Insert(const T& data)
	{
		KeyofT kt;
		Hash hs;
		auto it = Find(kt(data));
		if (it!=End())
		{
			return {it, false};
		}

		if (_n >= _tables.size())
		{
			vector<Node*> newtable(__stl_next_prime(_tables.size() + 1));
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t Hashi = hs(kt(cur->_data)) % newtable.size();
						cur->_next = newtable[Hashi];
						newtable[Hashi] = cur;
						cur = next;
					}
				}
				_tables[i] = nullptr;
			}

			_tables.swap(newtable);
		}

		Node* newnode = new Node(data);
		size_t Hashi = hs(kt(data)) % _tables.size();
		newnode->_next = _tables[Hashi];
		_tables[Hashi] = newnode;

		_n++;

		return make_pair(Iterator(newnode,this),true);
	}

	Iterator Find(const K& key)
	{
		KeyofT kot;
		Hash hs;
		size_t hashi = hs(key) % _tables.size();
		Node* cur = _tables[hashi];
		while (cur)
		{
			if (kot(cur->_data) == key)
				return { cur, this };

			cur = cur->_next;
		}

		return End();
	}

	bool Erase(const K& key)
	{
		KeyofT kot;
		Hash hs;
		size_t hashi = hs(key) % _tables.size();
		Node* prev = nullptr;
		Node* cur = _tables[hashi];
		while (cur)
		{
			if (kot(cur->_data) == key)
			{
				if (prev == nullptr)
				{
					_tables[hashi] = cur->_next;
				}
				else
				{
					prev->_next = cur->_next;
				}

				delete cur;

				return true;
			}

			prev = cur;
			cur = cur->_next;
		}

		return false;
	}


private:
	vector<Node*> _tables;
	size_t _n;
};